Masala #0318

Xotira 16 MB Vaqt 500 ms Qiyinchiligi 59 %
14

  

So’rovlarni tartiblash 2

Sizga N uzunlikdagi A massivi berilgan. Massiv ustida bajarish uchun Q ta so’rov berilgan. Har bir so’rov quyidagilardan biri bo’lishi mumkin:

  1. L R X : Massivning [L, R] indekslari oralig’idagi barcha elementga X sonini qo’shish
  2. L R X : Massivning [L, R] indekslari oralig’idagi barcha elementni qiymatini X ga almashtirish

Berilgan barcha so’rovlar massiv ustida bajarilishi kerak.

Sizga so’rovlarning bajarilish tartibini o’zgartirishga ruxsat etiladi. So’rovlar oxirida A massivning hosil qilish mumkin bo’lgan leksikografik eng katta qiymatini aniqlang.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son, N(1 ≤ N ≤ 105) va Q(1 ≤ Q ≤ 105) kiritiladi.

Ikkinchi satrda N ta butun son, A(-105 ≤ Ai ≤ 105) massiv elementlari kiritiladi.

Keyingi qatordan boshlab Q ta qatorda 4 tadan butun son, so’rov turi({1,2}), L, R(1 ≤ L ≤ R ≤ N), X(-105 ≤ X ≤ 105) kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylining yagona satrida N ta butun son, A massiv ustida barcha so’rovlarni bajargandan so’ng hosil qilish mumkin bo’lgan leksikografik eng katta massivni chop eting.


Misollar
# input.txt output.txt
1
5 3
1 2 3 4 5
1 3 4 2
2 1 2 3
1 4 5 -6
3 3 5 0 -1 
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin